DROPS

Document

DOI: 10.4230/OASIcs.ICCSW.2012.142

Search-Based Ambiguity Detection in Context-Free Grammars

Authors: Naveneetha Vasudevan and Laurence Tratt

Published in: OASIcs, Volume 28, 2012 Imperial College Computing Student Workshop

Abstract

Context Free Grammars (CFGs) can be ambiguous, allowing inputs to be parsed in more than one way, something that is undesirable for uses such as programming languages. However, statically detecting ambiguity is undecidable. Though approximation techniques have had some success in uncovering ambiguity, they can struggle when the ambiguous subset of the grammar is large. In this paper, we describe a simple search-based technique which appears to have a better success rate in such cases.

Cite as

Naveneetha Vasudevan and Laurence Tratt. Search-Based Ambiguity Detection in Context-Free Grammars. In 2012 Imperial College Computing Student Workshop. Open Access Series in Informatics (OASIcs), Volume 28, pp. 142-148, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{vasudevan_et_al:OASIcs.ICCSW.2012.142,
  author =	{Vasudevan, Naveneetha and Tratt, Laurence},
  title =	{{Search-Based Ambiguity Detection in Context-Free Grammars}},
  booktitle =	{2012 Imperial College Computing Student Workshop},
  pages =	{142--148},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-48-4},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{28},
  editor =	{Jones, Andrew V.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICCSW.2012.142},
  URN =		{urn:nbn:de:0030-drops-37788},
  doi =		{10.4230/OASIcs.ICCSW.2012.142},
  annote =	{Keywords: Ambiguity, Parsing}
}

Search Results

Documents authored by Vasudevan, Naveneetha

Search-Based Ambiguity Detection in Context-Free Grammars

Abstract

Cite as

Thanks for your feedback!

Could not send message